Google Code Jam/2010/1A/a/a.cpp

   1 #include <algorithm>
   2 #include <iostream>
   3 #include <iterator>
   4 #include <sstream>
   5 #include <fstream>
   6 #include <cassert>
   7 #include <climits>
   8 #include <cstdlib>
   9 #include <cstring>
  10 #include <string>
  11 #include <cstdio>
  12 #include <vector>
  13 #include <cmath>
  14 #include <queue>
  15 #include <deque>
  16 #include <stack>
  17 #include <list>
  18 #include <map>
  19 #include <set>
  20
  21 using namespace std;
  22
  23 template <class T> string toStr(const T &x){
  24 stringstream s; s << x; return s.str();
  25 }
  26
  27 template <class T> int toInt(const T &x){
  28 stringstream s; s << x; int r; s >> r; return r;
  29 }
  30
  31 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  32 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  33 #define D(x) cout << #x " = " << (x) << endl
  34
  35 const double EPS = 1e-9;
  36 int cmp(double x, double y, double tol = EPS){
  37   return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  38 }
  39
  40
  41 char mat[55][55];
  42
  43 int di[] = {+0, +1, +1, +1};
  44 int dj[] = {+1, +1, +0, -1};
  45
  46 void solve(){
  47   int n, k;
  48   cin >> n >> k;
  49   for (int j = n - 1; j >= 0; --j){
  50     for (int i = 0; i < n; ++i){
  51       cin >> mat[i][j];
  52     }
  53   }
  54
  55   for (int i = n - 1; i >= 0; --i){
  56     for (int j = 0; j < n; ++j){
  57       if (mat[i][j] == '.') continue;
  58       int k = i + 1;
  59       while (k < n and mat[k][j] == '.') k++;
  60       swap(mat[i][j], mat[k - 1][j]);
  61     }
  62   }
  63
  64   int winners = 0;
  65   for (int i = 0; i < n; i++){
  66     for (int j = 0; j < n; ++j){
  67       if (mat[i][j] == '.') continue;
  68       for (int d = 0; d < 4; ++d){
  69         int ni = i + (k - 1) * di[d];
  70         int nj = j + (k - 1) * dj[d];
  71         if (0 <= ni and ni < n and 0 <= nj and nj < n){
  72           bool ok = true;
  73           for (int p = 0; p < k; ++p){
  74             if (mat[i + p * di[d] ][ j + p * dj[d] ] != mat[i][j]){
  75               ok = false;
  76               break;
  77             }
  78           }
  79           if (ok){
  80             winners |= (mat[i][j] == 'R' ? 1 : 2);
  81           }
  82         }
  83       }
  84     }
  85   }
  86
  87   // For(i, 0, n){
  88   //   For(j, 0, n){
  89   //     cout << mat[i][j];
  90   //   }
  91   //   cout << endl;
  92   // }cout << endl;
  93   string s;
  94   if (winners == 0){
  95     s = "Neither";
  96   }else if (winners == 1){
  97     s = "Red";
  98   }else if (winners == 2){
  99     s = "Blue";
 100   }else if (winners == 3){
 101     s = "Both";
 102   }
 103   printf("%s\n", s.c_str());
 104 }
 105
 106 int main(){
 107   int T;
 108   cin >> T;
 109   for (int i = 0; i < T; ++i){
 110     printf("Case #%d: ", i + 1);
 111     solve();
 112   }
 113   return 0;
 114 }